Nowadays images appear routinely in massively distributed printed matter, such as books, magazines, newspapers, printer outputs and fax documents. Images appear also routinely in widely accessible web pages, and multimedia files on the Internet and in storage media such as CD-ROM and DVD. Associated with the widespread circulation of images are issues of copyright infringement, authentication and privacy, so it is often desirable to include within the images data such as company identity, owner information, creation date and time, for copyright protection and authentication purposes. Such embedded data has been referred to as “watermarking data”. The embedded object may for example be an image, a video sequence, an audio clip, a speech file, or a fax document. In the case that the embedded data is an image, the watermark may be visible or invisible, and the present invention is particularly concerned with invisible watermarks.
In many such images, each pixel takes one of many tone values. Such an image with at least three tone values, and normally many more, such as 256 tone values, is here referred to as a multitone image or grey scale image.
Quite a number of watermarking methods are known for natural grey scale images, so it is now possible to hide large amounts of data without suffering a great loss of image quality. For such algorithms, an important issue is the “robustness” of the watermarking, that is how hard it is for a third party to remove the watermark.
However, few, if any, known watermarking algorithms can be applied to “halftone” images—that is images in which each position (pixel) takes one of two values. Halftoning is a method often used to transform multi-tone images (typically with 256 levels) into images with two-tone colors (2 levels). Such methods are used widely in computer printers, newspaper/magazine/book publishing, fax machines, etc. From a distance, halftone images resemble images with multi-tones.
There are two main kinds of halftoning techniques, namely, ordered dithering (see B. E. Bayers, “An Optimum Method for Two Level Rendition of Continuous Tone Pictures,” Proc. of IEEE Int. Communication Conf., pp 2611–2615, 1973) and error diffusion (R. W. Floyd, L. Steinberg, “An Adaptive Algorithm for Spatial Greyscale,” Proc. SID, pp. 75–77, 1976.). Ordered Dithering is a computationally simple and effective halftoning method, usually adopted in low-end printers. It compares the pixel intensities with some pseudo random threshold patterns or screens in order to determinate its 2-tone output.
Table 1 shows an example of a dithering screen (taken from L. M. Chen, H. M. Hang, “An Adaptive Inverse Halftoning Algorithm”, IEEE Trans. on Image Processing, Vol. 6, No. 8, August 1997), which will be used throughout this document. FIG. 4 shows an original 8 bit grey scale image, Lena, of size 512×512 that will be used throughout this paper. FIG. 12 is the halftoned version of Lena produced using ordered dithering.
TABLE 1“8 × 8 dispersed-dot” dither matrix 032 840 234104248165624501858261244 4361446 6386028422062304422 3351143 133 94151195927491757251547 7391345 5376331452361294321
Error diffusion is an advanced technique usually used in high-end printers. It is more complicated than ordered dithering, but it can generate halftone images with higher visual quality. It is a single pass algorithm. In error diffusion, the halftoning output is obtained by comparing the image pixels with a fixed threshold. However, the halftoning error is fed back to its adjacent neighbors so that each image pixel has effectively an adaptive threshold. The error feedback helps to maintain approximately equal local intensity average between the original multi-tone images and the corresponding halftone images. An essential component of error diffusion is its error feedback kernel. Different kernels can have quite different behavior. Two commonly used error feedback kernels are used in this article. They are the Jarvis kernel and the Steinberg kernel shown in Tables 2 and 3.
For illustration, halftoned images of “Lena” processed with the Jarvis and Steinberg kernels are shown in FIG. 16 and FIG. 5 respectively. The Jarvis kernel has a large support and tends to give halftone images with high contrast and coarse texture. The Steinberg kernel has smaller support and gives halftone images with fine texture and good contrast. In each case, each element of tables 2 and 3 refers to a respective pixel. The element with an entry marked “x” refers to the pixel currently being processed. Each numerical entry shows the weighting of the effect on the pixel presently being processed from the error caused by halftoning in the pixel with the numerical entry.
TABLE 2The Jarvis kernel135313575357X
TABLE 3The Steinberg kernel1357X
It is well known that most image processing techniques such as filtering or resizing cannot be applied to a halftone image to produce another halftone image with good visual quality. Watermarking is not an exception. Most, if not all, existing watermarking schemes for natural images cannot be applied to halftone images due to the special characteristics of halftone images. Halftone images contain only two tones and have large amount of high frequency noise resulting in very little intensity redundancy. The halftone image pixels take on only two possible values, typically 0 and 255 (or black and white). Most existing watermarking schemes for natural images would generate images that require 8 bits to represent and will take on values other than 0 and 255.
However, there are some existing techniques for halftone image watermarking. It is known to use two different dithering matrices for the halftone generation (see Z. Baharav, D. Shaked, “Watermarking of Dither Halftoned Images”, Proc. of SPIE Security and Watermarking of Multimedia Contents, pp. 307–313, January 1999) such that the different statistical properties due to the two dithering matrices can be detected in the future. It is also known to use stochastic screen patterns (see K. T. Knox, “Digital. Watermarking Using Stochastic Screen Patterns”, U.S. Pat. No. 5,734,752) and conjugate halftone screens (see S. G. Wang, “Digital Watermarking Using Conjugate Halftone Screens”, U.S. Pat. No. 5,790,703) in which two screens are used to form two halftone images and the data is embedded through the correlations between two screens. The embedded pattern can be viewed when the two halftone images are overlaid. It is further known to embed some data in the angular orientation of circularly asymmetric halftone dot patterns that are written into the halftone cells of digital halftone images (see R. T. Tow, “Methods and Means for Embedding Machine Readable Digital Data in Halftone Images”, U.S. Pat. No. 5,315,098).
As most halftone images are printed on paper, there are few possible digital attacks on the watermarked halftone images, even though there can be many physical attacks on the paper on which the images are printed. For this reason, rather than robustness, the data hiding capacity and the image quality are much more important issues for watermarking halftone images than for grey-tone images. One common characteristic of the above known watermarking methods is that they cannot embed a large amount of data in a halftone image without significant perceptual distortion.